Data-Structures-and-Algorithms/Python/Flattening of a linked list/solution.py at main · codemistic/Data-Structures-and-Algorithms · GitHub

Name: Data-Structures-and-Algorithms/Python/Flattening of a linked list/solution.py at main · codemistic/Data-Structures-and-Algorithms · GitHub
Rating: 4.5 (2893 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
# Python3 program for flattening a Linked List


classNode():
def__init__(self, data):
self.data=data
self.right=None
self.down=None


classLinkedList():
def__init__(self):

# head of list
self.head=None

# Utility function to insert a node at beginning of the
# linked list
defpush(self, head_ref, data):

# 1 & 2: Allocate the Node &
# Put in the data
new_node=Node(data)

# Make next of new Node as head
new_node.down=head_ref

# 4. Move the head to point to new Node
head_ref=new_node

# 5. return to link it back
returnhead_ref

defprintList(self):

temp=self.head
while(temp!=None):
print(temp.data, end=" ")
temp=temp.down

print()

# An utility function to merge two sorted linked lists
defmerge(self, a, b):
# if first linked list is empty then second
# is the answer
if(a==None):
returnb

# if second linked list is empty then first
# is the result
if(b==None):
returna

# compare the data members of the two linked lists
# and put the larger one in the result
result=None

if (a.data<b.data):
result=a
result.down=self.merge(a.down, b)
else:
result=b
result.down=self.merge(a, b.down)

result.right=None
returnresult

defflatten(self, root):

# Base Case
if(root==Noneorroot.right==None):
returnroot
# recur for list on right

root.right=self.flatten(root.right)

# now merge
root=self.merge(root, root.right)

# return the root
# it will be in turn merged with its left
returnroot


# Driver's code
if__name__=='__main__':
L=LinkedList()

'''
 Let us create the following linked list
 5 -> 10 -> 19 -> 28
 | | | |
 V V V V
 7 20 22 35
 | | |
 V V V
 8 50 40
 | |
 V V
 30 45
 '''
L.head=L.push(L.head, 30)
L.head=L.push(L.head, 8)
L.head=L.push(L.head, 7)
L.head=L.push(L.head, 5)

L.head.right=L.push(L.head.right, 20)
L.head.right=L.push(L.head.right, 10)

L.head.right.right=L.push(L.head.right.right, 50)
L.head.right.right=L.push(L.head.right.right, 22)
L.head.right.right=L.push(L.head.right.right, 19)

L.head.right.right.right=L.push(L.head.right.right.right, 45)
L.head.right.right.right=L.push(L.head.right.right.right, 40)
L.head.right.right.right=L.push(L.head.right.right.right, 35)
L.head.right.right.right=L.push(L.head.right.right.right, 20)

# Function call
L.head=L.flatten(L.head)

L.printList()